/*
 * One example for NOI CSP-J Lesson 4:
 * <https://courses.fmsoft.cn/plzs/noijunior-tree-data-structures.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2024 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <iostream>     // for cin and cout
#include <sstream>      // for ostringstream
#include <string>       // for stod()
#include <cassert>      // for assert()
#include <cstring>
#include <dirent.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <vector>       // for vector
#include <stack>        // for stack
#include <queue>        // for queue
using namespace std;
template <typename T>
class tree_node {
  public:
    T payload;                          // 节点负载
    std::vector<tree_node*> children;   // 子节点矢量

    // 节点的构造函数
    tree_node(const T& value) {
        payload = value;
    }

    // 节点的析构函数
    ~tree_node() {
        for (size_t i = 0; i < this->children.size(); i++) {
            delete children[i];
            children[i] = nullptr;
        }
    }

    // 返回节点的子节点数量。
    size_t nr_children(const tree_node* node) const {
        return node->children.size();
    }

    // 深度优先（depth-first）前序遍历（递归实现）
    template <typename context, typename visitor_func>
    void dfs_preorder_r(context* ctxt, visitor_func visitor) const
    {
        // call the visitor for the current node
        visitor(ctxt, payload);

        size_t nr_children = children.size();
        for (size_t i = 0; i < nr_children; i++) {
            children[i]->dfs_preorder_r(ctxt, visitor);
        }
    }
    // 深度优先（depth-first）后序遍历（递归实现）
    template <typename context, typename visitor_func>
    void dfs_pastorder_r(context* ctxt, visitor_func visitor) const
    {
        size_t nr_children = children.size();
        for (size_t i = 0; i < nr_children; i++) {
            children[i]->dfs_pastorder_r(ctxt, visitor);
        }

        // call the visitor for the current node
        visitor(ctxt, payload);
    }

    // 深度优先（depth-first）前序遍历（迭代实现）
    template <typename context, typename visitor_func>
    void dfs_preorder_i(context* ctxt, visitor_func visitor) const
    {
        std::stack<const tree_node*> stack;
        stack.push(this);

        while (!stack.empty()) {
            const tree_node* node = stack.top();
            stack.pop();

            // call the visitor for current node
            visitor(ctxt, node->payload);

            size_t nr_children = node->children.size();
            for (size_t i = 0; i < nr_children; i++) {
                stack.push(node->children[nr_children - i - 1]);
            }
        }
    }

    // 广度优先（breadth-first）遍历
    template <typename context, typename visitor_func>
    void bfs(context* ctxt, visitor_func visitor) const
    {
        std::queue<const tree_node*> queue;
        queue.push(this);

        while (!queue.empty()) {
            const tree_node* node = queue.front();
            queue.pop();

            // call the visitor for current node
            visitor(ctxt, node->payload);

            size_t nr_children = node->children.size();
            for (size_t i = 0; i < nr_children; i++) {
                queue.push(node->children[i]);
            }
        }
    }

    // 在当前节点的子节点头部压入新节点，返回新节点
    tree_node* push_front(const T& value)
    {
        // Create a new node with the given value
        tree_node* child = new tree_node(value);
        // Push the pointer to the front of children
        children.insert(children.begin(), child);
        return child;
    }

    // 弹出当前节点头部的子节点
    void pop_front()
    {
        if (children.size() > 0) {
            delete children.front();
            children.erase(children.begin());
        }
    }

    // 在当前节点的子节点尾部压入新节点，返回新节点
    tree_node* push_back(const T& value)
    {
        // Create a new node with the given value
        tree_node* child = new tree_node(value);
        // Push the pointer to the front of children
        children.push_back(child);
        return child;
    }

    // 弹出当前节点尾部的子节点
    void pop_back()
    {
        if (children.size() > 0) {
            delete children.back();
            children.pop_back();
        }
    }
};
/*
// 为支持自定义的 ostream 操作器（manipulator）indent() 而定义一个新的结构类型。
struct _Spaces { unsigned n; };

// 该操作器可以如此使用：cout << indent(3) << endl;
inline _Spaces indent(unsigned level) {
    return { level };
}

// 重载 ostream 的 << 运算符，其左值类型为 ostream&，右值类型为 _Space。
// 从而支持 cout << indent(3) 这样的用法。
inline ostream& operator<<(ostream& os, _Spaces _s) {
    for (unsigned i = 0; i < _s.n; i++) {
        os << ' ';
    }

    return os;
}
*/
/*
  该函数递归读取目录中的目录项并列出，效果如下：

  ./lesson-4/
   in.txt
   out.txt
   Makefile
   generic-tree.cpp
   students.bin
   fstream-binary.cpp
   binary-tree.cpp
   readdir.cpp
   iostream-rdbuf.cpp
  ./lesson-3/
   Makefile
   simple-vector.cpp
   doubly-linked-list.cpp
   singly-linked-list.cpp
   singly-circular-linked-list.cpp
*/
struct nod{
    string path;
    size_t size;
    time_t ctime;
};
using my_tree_node = tree_node<struct nod>;
void list_dir_entries_and_tree(/*输出时候需要*/unsigned level, const string& path, my_tree_node* root)
{
    DIR*    dir;
    struct  dirent* dir_ent;

    dir = ::opendir(path.c_str());
    if (dir == nullptr) {
        cerr << "Failed to open directory: " << path << endl;//标准错误
        return;
    }

    //cout << indent(level * 2) << path << "/" << endl;
    //初始路径 ./

    while ((dir_ent = ::readdir(dir)) != nullptr) {
        // 跳过 . 和 ..，否则会无限递归
        if (strcmp(dir_ent->d_name, ".") == 0//对比字符串，一样跳过
                || strcmp(dir_ent->d_name, "..") == 0)
            continue;

        // 组装完整文件路径
        string full_path = path + "/" + dir_ent->d_name;
        //路径，例如./source/python + / + endl

        struct stat my_stat;

        if (::stat(full_path.c_str(), &my_stat) < 0 ){
            cerr << "Failed to stat file: " << full_path << endl;
            continue;
        }

        struct nod n_stat={
            full_path,my_stat.st_size,my_stat.st_ctime
        };

        if (S_ISDIR(my_stat.st_mode)) {
            root = root->push_back(n_stat);
            list_dir_entries_and_tree(level + 1, full_path, root);
        }
        else {
            //cout << indent(level * 2 + 1) << dir_ent->d_name << endl;
            root->push_front(n_stat);
        }

        // XXX struct stat 结构中的 st_size 字段包含有文件的大小（字节为单位）。
        // XXX struct stat 结构中的 st_ctime 字段包含有文件的最后修改时间。
    }

    ::closedir(dir);
}
//using namespace std;
struct context{
    const struct nod* value;
};

void visitor_smallest(context* ctxt, const struct nod& value) {
    if(ctxt->value==nullptr){
        ctxt->value = &value;
    }
    else{
        if(value.size < ctxt->value->size){
            ctxt->value = &value;
        }
    }
}
int main(int argc, const char* argv[])
{
   
    //test_tree_node();
    string start;
    if (argc > 1)
        start = argv[1];
    else
        start = ".";

    //list_dir_entries(0, start);
    struct stat my_stat;
    if (::stat(start.c_str(), &my_stat) < 0 ){
        cerr << "Failed to stat file: " << start << endl;
        return 1;
    }
    struct nod first_stat={
        start,my_stat.st_size,my_stat.st_ctime
    };
    my_tree_node* root = new my_tree_node(first_stat);
    list_dir_entries_and_tree(0,start,root);
    struct visitor_bigest {
        void operator() (context* ctxt, const struct nod& value) {
            if(ctxt->value==nullptr){
                ctxt->value = &value;
            }
            else{
                if(value.size > ctxt->value->size){
                    ctxt->value = &value;
                }
            }
        }
    };

    context ctxt = { nullptr };
    root->dfs_preorder_i(&ctxt, visitor_bigest{});
    cout << "The largest file: " << ctxt.value->path << " (" << ctxt.value->size << " Bytes)" << endl;

    ctxt = { nullptr };
    root->dfs_pastorder_r(&ctxt, visitor_smallest);
    cout << "The smallest file: " << ctxt.value->path << " (" << ctxt.value->size << " Bytes)" << endl;

    ctxt = { nullptr };
    root->bfs(&ctxt, [](context* ctxt, const struct nod& value){
            if(ctxt->value==nullptr){
                ctxt->value = &value;
            }
            else{
                if(value.ctime > ctxt->value->ctime){
                    ctxt->value = &value;
                }
            }
            });
    cout << "The latest modified file: " << ctxt.value->path << endl;
}

